package com.chapter4.graph.direct;

import java.util.Stack;

/**
 * 
* @ClassName: KosarajuSCC 
* @Description: Kosaraju强连通性算法
* @author minjun
* @date 2015年3月5日 下午2:32:29 
*
 */
public class KosarajuSCC {
	
	private boolean[] marked;
	
	//逆后序
	private Stack<Integer> reversePost;
	
	//连通标识
	private int[] id;
	
	//连通分量总数
	private int count;
	
	public KosarajuSCC(Digraph d){
		int len=d.V();
		marked=new boolean[len];
		reversePost=new Stack<Integer>();
		Digraph reverse=d.reverse();
		for(int i=0;i<len;i++){
			if(!marked[i]){
				reverseDFS(reverse,i);
			}
		}
		
		id=new int[len];
		marked=new boolean[len];
		while(!reversePost.isEmpty()){
			int i=reversePost.pop();
			if(!marked[i]){
				dfs(d,i);
				count++;
			}
		}
	}

	private void reverseDFS(Digraph reverse, int v) {
		marked[v]=true;
		for(int w:reverse.adj(v)){
			if(!marked[w]){
				reverseDFS(reverse, w);
			}
		}
		reversePost.push(v);
	}

	private void dfs(Digraph d, int v) {
		marked[v]=true;
		id[v]=count;
		for(int w:d.adj(v)){
			if(!marked[w]){
				dfs(d, w);
			}
		}
	}
	
	/**
	 * 
	* @Title: connected 
	* @Description: 两个点是否强连通 
	* @param @param v
	* @param @param w
	* @param @return    设定文件 
	* @return boolean    返回类型 
	* @throws
	 */
	public boolean connected(int v,int w){
		return id[v]==id[w];
	}
	
	/**
	 * 
	* @Title: id 
	* @Description: 所属强连通标识 
	* @param @param v
	* @param @return    设定文件 
	* @return int    返回类型 
	* @throws
	 */
	public int id(int v){
		return id[v];
	}
	
	/**
	 * 
	* @Title: count 
	* @Description: 连通分量总数 
	* @param @return    设定文件 
	* @return int    返回类型 
	* @throws
	 */
	public int count(){
		return count;
	}
}
